//
//bool hasPathSum(struct TreeNode* root, int targetSum) {
//    if (root == NULL)
//        return false;
//    if (root->val == targetSum && root->right == NULL && root->left == NULL)
//        return true;
//    return hasPathSum(root->left, targetSum - root->val)
//        || hasPathSum(root->right, targetSum - root->val);
//


//
//class Solution {
//public:
//    long long prev = LLONG_MIN;
//    bool isValidBST(TreeNode* root) {
//        return dfs(root);
//    }
//
//    bool dfs(TreeNode* root)
//    {
//        if (root == nullptr) return true;
//        if (root->left && !dfs(root->left)) return false;
//        if (root->val <= prev)   return false;
//        prev = root->val;
//        return dfs(root->right);
//    }
//}; }




class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, bool> hash;
        for (auto& str : wordDict)
            hash[str] = true;
        int n = s.size();
        s = " " + s;

        vector<int> dp(n + 1);
        dp[0] = true;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j >= 1; j--)
            {
                if (hash[s.substr(j, i - j + 1)] && dp[j - 1])
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};